package basic.study.wantOffer.chapter3;

import java.util.ArrayList;

/**
 * @ClassName Problem34
 * @Description 二叉树中和为某一值的路径
 * @Company inspur
 * @Author Kevin
 * @Date 2020/5/23 9:55
 * @Version 1.0
 */
public class Problem34 {



    public void findPath(TreeNode root, int k) {
        if (root == null) return;
        ArrayList<Integer> list = new ArrayList<Integer>();
        dfs(root, k, list);
    }

    /**
     * 递归+回溯
     * @param node
     * @param k
     * @param list
     */
    private void dfs(TreeNode node, int k, ArrayList<Integer> list) {
        if (node == null) return;
        list.add(node.val);
        k -= node.val;
        if (node.left == null && node.right == null && k == 0) {
            for (Integer i : list) {
                System.out.println(i + " ");
            }
            System.out.println();
        } else {
            dfs(node.left, k, list);
            dfs(node.right, k, list);
        }
        list.remove(list.size() -1);


    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
    }
}
